import java.util.HashMap;
import java.util.Map;

/**
 * @program: LeetCode
 * @description: LeetCode : 138. 复制带随机指针的链表
 * @author: WXY
 * @create: 2023-02-08 16:49
 * @Version 1.0
 **/
public class Num138_copyRandomList {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList1(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }

    public Node copyRandomList(Node head) {
        if (head == null) return head;
        Node cur = head;
        //完成链表节点的复制，1->2->3 ----   1->1->2->2->3->3
        while (cur != null) {
            Node tempNode = new Node(cur.val);
            tempNode.next = cur.next;
            cur.next = tempNode;
            cur = cur.next.next;
        }
        //完成链表的连接
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        //将链表分开
        Node pre = head, res = head.next;
        cur = head.next;
        while (cur.next != null) {
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;
            cur = cur.next;
        }
        pre.next = null;
        return res;
    }


}
